#define _CRT_SECURE_NO_WARNINGS 1
#include <cstdio>
#include <iostream>
#include <stack>

typedef int TNDataType;

typedef struct TreeNode
{
	TNDataType val;
	TreeNode* left;
	TreeNode* right;
}TreeNode;

TreeNode* BuyTreeNode(int val)
{
	TreeNode* newnode = (TreeNode*)malloc(sizeof(TreeNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->val = val;
	newnode->left = NULL;
	newnode->right = NULL;
}

void PostOrder(TreeNode* root)
{
	std::stack<TreeNode*> st;
	TreeNode* prev = NULL;
	TreeNode* cur = root;

	while (cur || !st.empty())
	{
		while (cur)
		{
			st.push(cur);
			cur = cur->left;
		}

		TreeNode* top = st.top();
		if (top->right == nullptr || top->right == prev)
		{
			std::cout << top->val << " ";
			st.pop();
			prev = top;
		}
		else
		{
			cur = top->right;
		}
	}
}


void TestPostOrder()
{
	TreeNode* p1 = BuyTreeNode(1);
	TreeNode* p2 = BuyTreeNode(2);
	TreeNode* p3 = BuyTreeNode(3);
	TreeNode* p4 = BuyTreeNode(4);
	TreeNode* p5 = BuyTreeNode(5);
	TreeNode* p6 = BuyTreeNode(6);
	TreeNode* p7 = BuyTreeNode(7);

	p1->left = p2;
	p1->right = p3;
	p3->left = p4;
	p3->right = p5;
	p2->left = p6;
	p2->right = p7;

	PostOrder(p1);
}



int main()
{
	TestPostOrder();
	return 0;
}